Technical Field
This disclosure relates to processor cache operation, and more particularly to cache replacement mechanisms.
Description of the Related Art
Modern processors use a number of cache memory hierarchies in an effort to expedite data retrieval from main memory. In particular, most all processor cores will have at least a level one (L1) cache that is proximal to the core. In many cases, and especially in multi-core designs, a processor will also have a level two (L2) cache, and in some cases a level three (L3) cache. The L2 and L3 caches are in many cases shared among the various processor cores. The multiple cache hierarchies allow a processing system to keep copies of data that is accessed frequently in the local faster cache memory hierarchy, rather than having to access main memory which is typically slower.
However, even with the increasing size of the L2 and L3 caches, they do fill up, and older cache lines need to be evicted. Generally speaking it is typically the case that the least recently used (LRU) cache line is the line that is evicted. There have been many LRU algorithms used to determine which cache line to evict. For example, round robin algorithms among others are frequently used. Many of these algorithms do work. However, many of them have drawbacks that evict cache lines that for a variety of reasons should have been kept.